﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution31
{//计算字典序,感觉就是数字的大小，比如321>123
    //这个例子很好，123546 就是 123465 的下一个排列
    public void NextPermutation(int[] nums)
    {
        //先找6
        int Bigest = 0;
        int smaller = 0;//4
        int bigger = 0;//5

        for (int i = nums.Length-1; i >0; i--)
        {

            if (nums[i] > nums[i - 1])//Bigest后面的数是降序
                                      //i=0,i-1<0,说明已经是最大的，654321
            {
                Bigest =i;
                smaller = i - 1;
                break;
            }
        
        }
        //if (Bigest == 0)//说明逆序了smaller=0,下面的步骤跳过了
        //{
        //    Reverse(nums, Bigest);
        //    return;
        //}


        for (int i = nums.Length - 1; i >= 0; i--)
        {

            if (nums[i] > nums[smaller])//bigger后面的数都小于smaller，所以交换之后也是降序
            {
                bigger = i;
                swap(nums,bigger, smaller);//123564

                break;
            }

        }
        ////123564,变为1235 46，从Bigest开始逆序
        Reverse(nums, Bigest);

    }

    private void Reverse(int[] nums, int start)//反转数组
    {
        int left=start;
        int right= nums.Length-1;
        while (left < right)
        {
            swap(nums, left, right);
            left++;
            right--;
        }
        
       

    }

    private void swap(int[] nums, int bigger, int smaller)
    {
       int temp = nums[smaller];
        nums[smaller] = nums[bigger]; nums[bigger] = temp;
    }

    public double Permutation(int[] nums)//计算字典序
    {
        double res = 0;
        int m = nums.Length;
        for (int i = 0; i < nums.Length; i++)
        {
            //先算一下10的几次方
            double index = Math.Pow(10,m-i-1);
            res += index * nums[i];
        }
        return res;
    }
}


class Program31
{
    static void Main31(string[] args)
    {
        Solution31 solution = new Solution31();
        int[] nums = [1, 2, 3];
        solution.NextPermutation(nums);

        for (int i = 0; i < nums.Length; i++)
        {
            Console.WriteLine(nums[i]);
        }

   double sort=     solution.Permutation(nums);
        Console.WriteLine("字典序是"+sort);


    }
}